// Chain Class implementation
#include "Chain.h"
#include <string>
#include "Helpers.h"
#include "Input.h"
#include <iostream>
using namespace std;

//----------------------------------------------------------------------------------
// Public
//----------------------------------------------------------------------------------

//----------------------------------------------------------------------------------
// Ctor: creates a chain from a given file
//----------------------------------------------------------------------------------
Chain::Chain(ChainParser &permutationsFile, InputVariables inputVars)
{
	try
	{
		m_Graph = new Graph(inputVars.numberOfPairsInImprovedGreedy, inputVars.numberOfIterationsForVertexSearch);
	}
	catch(std::bad_alloc *e)
	{
		e = NULL;
		Logger::LogMessage("failed creating chain object, program out of memory");
		throw(new GraphColoringException("memomry allocation failed"));
	}

	// Work with static vertex directory
	m_VertexDirectory = NULL;
	
	//create the groups and update the vertices and the graph to the correct state
	CreateGroups(permutationsFile);
	
	m_LastGroupFromPermutaionsIndex = -1; //none of the groups are from permutations
}

//----------------------------------------------------------------------------------
// Ctor: creates a chain from the provided graph & vertex directory
//----------------------------------------------------------------------------------
Chain::Chain(Graph *graph, VertexDirectory *dir)
{
	m_Graph = graph;
	m_VertexDirectory = dir;
	m_Length = 0;
	m_LastGroupFromPermutaionsIndex = -1; //none of the groups are from permutations
}

//----------------------------------------------------------------------------------
// Dtor
//----------------------------------------------------------------------------------
Chain::~Chain()
{
	list<Group*>::iterator it;
	for (it = m_Groups.begin(); it != m_Groups.end(); it++)
	{
		if ((*it)->Size() > 0)
			delete (*it);
	}

	delete m_Graph;

}
//----------------------------------------------------------------------------------
// ChainGroupNames returns a set of the names of the groups in the chain
//----------------------------------------------------------------------------------
set<int> Chain::ChainGroupNames()
{
	return m_GroupNames;
}

//----------------------------------------------------------------------------------
// ChainGroups: returns a list of all the groups in this chain
//----------------------------------------------------------------------------------
list<Group*> Chain::ChainGroups()
{
	return m_Groups;
}

//----------------------------------------------------------------------------------
// GetGroup: retuns a pointer to the group with groupId 
// (If the group is not in the chain, returns NULL)
//----------------------------------------------------------------------------------
Group* Chain::GetGroup(int groupId)
{
	list<Group*>::iterator it;
	for ( it=m_Groups.begin() ; it != m_Groups.end(); it++ )
	{
		if ((*it)->GetGroupName() == groupId)
		{
			return *it;
		}
	}
	return NULL;
}

//----------------------------------------------------------------------------------
// AddGroup: Adds the group to the list of groups
//----------------------------------------------------------------------------------
void Chain::AddGroup(Group *group)
{
	
	//insert the group to it's right place in the chain 
	//keep the chain sorted from largest to smallest
	list<Group*>::iterator it = m_Groups.begin();
	for(; it != m_Groups.end(); it++)
	{
		if (group->Size() > (*it)->Size())
			break;
	}
	m_Groups.insert(it, group);
	
	//m_Groups.push_back(group);
	m_GroupNames.insert(group->GetGroupName());
	m_Length++;
	
	//update the graph related to the chain: the vertices of the group
	// are not in the graph any more.
	m_Graph->RemoveGroupVerticesFromGraph(group);
}

//----------------------------------------------------------------------------------
// GetGraph: returns the graph related to this chain
//----------------------------------------------------------------------------------
Graph* Chain::GetGraph()
{
	return m_Graph;
}

//----------------------------------------------------------------------------------
// GetDirectory: returns the vertex directory related to this chain
//----------------------------------------------------------------------------------
VertexDirectory *Chain::GetDirectory()
{
	return m_VertexDirectory;
}

//----------------------------------------------------------------------------------
// Begin: returns iterator to the beginning of the list of groups
//----------------------------------------------------------------------------------
list<Group*>::iterator Chain::Begin()
{
	return m_Groups.begin();
}

//----------------------------------------------------------------------------------
// NonPermutationsGroupsBegin: returns an iterator to the 1st group that isn't
// from the permutations part (or to End if none exist)
//----------------------------------------------------------------------------------
list<Group*>::iterator Chain::NonPermutationsGroupsBegin()
{
	list<Group*>::iterator it = m_Groups.begin();
	for (int i = 0; i <= m_LastGroupFromPermutaionsIndex; i++)
	{
		it++;
	}

	return it;
}

//----------------------------------------------------------------------------------
// End: returns iterator that points to after the last element in the list of groups
//----------------------------------------------------------------------------------
list<Group*>::iterator Chain::End()
{
	return m_Groups.end();
}

//----------------------------------------------------------------------------------
// Compare: compares this object to otherChain object.
// If this < otherChain, return -1 (some negative number)
// if this > otherChain, returns 1 (some positive number)
// otherwise returns 0
// the "bigger than" relationship of chains is defined as following:
// this >= otherChain iff for every prefix of this object, the number of vertices in 
// the prefix is greater or equal to the number of vertices in the prefix of the same
// length in otherChain (length of a prefix = number of groups in the prefix).
// this > otherChain iff this >= otherChain && at least one of the prefixes of this 
// object contains more vertices than the prefix of the same length of otherChain.
// this == otherChain if every prefix of this object contains exactly the same 
// number of vertices as the prefix with the same length of otherChain.
//
// Important note: This method compares the number of vertices in prefixes. 2 chains
// may be considered equal even if they contain different groups.
//----------------------------------------------------------------------------------
int Chain::Compare(Chain *otherChain)
{
	int length = this->m_Length > otherChain->m_Length ? this->m_Length : otherChain->m_Length;
	return CompareSubChains(otherChain, length);
}

//----------------------------------------------------------------------------------
// CompareSubChains: compares this object to otherChain object, just like the 
// Compare method.
// The only difference is, this method compares only the prefixes of length <= length
// (COmpares only the prefix of both chains, of length <= length)
//
// Important note: This method compares the number of vertices in prefixes. 2 chains
// may be considered equal even if they contain different groups.
//----------------------------------------------------------------------------------
int Chain::CompareSubChains(Chain* otherChain, int length)
{
	list<Group*>::iterator itA;
	list<Group*>::iterator itB = otherChain->Begin();
	// # of vertices in the prefix of this chain
	int verticesA = 0;
	// # of vertices in the prefix of other chain
	int verticesB = 0;
	// number of groups we've already compared
	int comparedLength = 1;
	for (itA = this->Begin(); itA != this->End(); itA++)
	{
		verticesA += (*itA)->Size();
		verticesB += (*itB)->Size();
		if (verticesA > verticesB)
		{	// this > otherChain
			return BIGGER;
		}
		if (verticesA < verticesB)
		{	// this < otherChain
			return SMALLER;
		}
		itB++;
		comparedLength++;
		// check if we've reached the end of otherChain
		if ((itB == otherChain->End()) || (comparedLength > length))
		{	// we checked all the prefixes of chainB
			// move the iterator of this object to the next group
			itA++;
			break;
		}
	}
	// check if this chain is longer
	if ((itB == otherChain->End()) && (itA != this->End()))
	{	
		return BIGGER;
	}
	if ((itB != otherChain->End()) && (itA == this->End()))
	{	
		return SMALLER;
	}
	// chains are of the same length, all prefixes contain the same number of vertices
	return EQUAL;
}

//----------------------------------------------------------------------------------
// Compare: (overloaded version)
// compares this object to an array which contains group sizes.
// 
// @param chainGroupSizes
//		 an array that conatins the group sizes
// @param arrayLen
//		array langth
//
// @return
//		If this < chainGroupSizes, return -1 (some negative number)
//		if this > chainGroupSizes, returns 1 (some positive number)
//		otherwise returns 0
//
// the "bigger than" relationship of a chain and an arry of group sizes is as follows:
// this >= chainGroupSizes iff for every prefix of this object, the number of vertices in 
// the prefix is greater or equal to the number of vertices in the prefix of the same
// length in chainGroupSizes (length of a prefix = number of groups in the prefix).
// this > chainGroupSizes iff this >= otherChain && at least one of the prefixes of this 
// object contains more vertices than the prefix of the same length of otherChain.
// this == otherChain if every prefix of this object contains exactly the same 
// number of vertices as the prefix with the same length of otherChain.
//----------------------------------------------------------------------------------
int Chain::Compare(int* chainGroupSizes, int arrayLen)
{
	int verticesA = 0;	// # of vertices in the prefix of this chain
	int verticesB = 0;	// # of vertices in the prefix of Array

	int minLen = arrayLen < m_Length ? arrayLen : m_Length;
	list<Group*>::iterator itA = Begin();
	for (int i=0; i < minLen; i++, itA++)
	{
		verticesA += (*itA)->Size();
		verticesB += chainGroupSizes[i];
		if (verticesA > verticesB)
		{	
			return BIGGER; // this > Array Chain
		}
		if (verticesA < verticesB)
		{	
			return SMALLER; // this < Array Chain
		}
	}
	
	//if we are here, the two chains have the same prefix with length minLen.
	//so the better (bigger) chain is the one that is longer
	
	// check if this chain is longer
	if (m_Length >  arrayLen)
	{	
		return BIGGER;
	}
	if (m_Length <  arrayLen)
	{	
		return SMALLER;
	}
	
	// chains are of the same length, all prefixes contain the same number of vertices
	return EQUAL;
}

//----------------------------------------------------------------------------------
// PrintGroupData: Prints a list of the groups in this chain and their sizes
//----------------------------------------------------------------------------------
void Chain::PrintGroupData()
{
	string str;
	std::stringstream strStream;
	strStream <<"Chain data: \n";
	list<Group*>::iterator it;
	for ( it=m_Groups.begin() ; it != m_Groups.end(); it++ )
	{
		strStream << "Group #" <<(*it)->GetGroupName() << " : " << (*it)->Size() << "\n";
	}
	str = strStream.str();
	Logger::LogMessage(str);
}

//----------------------------------------------------------------------------------
//GetMaxGroupIndex: returns the highest group name in the chain
//----------------------------------------------------------------------------------
int Chain::GetMaxGroupIndex()
{

	set<int>::iterator it;
	int maxGroupName = -1;
	for (it = m_GroupNames.begin(); it != m_GroupNames.end(); it++)
	{
		if ((*it)>maxGroupName)
		{
			maxGroupName = *it;
		}
	}
	return maxGroupName;
}


//----------------------------------------------------------------------------------
// CloneFromVertexDirectory: returns a new chain which is a copy of this chain 
// object, with all vertex pointers from the given directory
//----------------------------------------------------------------------------------
Chain *Chain::CloneFromVertexDirectoryAndUpdateIt(VertexDirectory *directory)
{
	// First, update all the vertices in the new directory
	VertexDirectory::UpdateVertexDirectoryFromOther(m_VertexDirectory,directory);

	// Now rebuild all the data structures
	Graph* tempGraph = m_Graph->CloneFromDirectory(directory);
	Debug::PrintDebugMsg("Cloned graph");
	if (tempGraph == NULL)	//memory allocation failed
	{
		Logger::LogMessage("memory allocation failed in Chain::CloneFromVertexDirectoryAndUpdateIt. chain wasn't created.");
		return NULL;
	}
	Chain *newChain = NULL;
	try
	{
		newChain = new Chain(tempGraph, directory);
	}
	catch(std::bad_alloc *e) //memory allocation failed
	{
		e = NULL;
		Logger::LogMessage("memory allocation failed in Chain::CloneFromVertexDirectoryAndUpdateIt. chain wasn't created.");
		delete tempGraph;
		return NULL;
	}
	
	list<Group*>::iterator it;
	for (it = m_Groups.begin(); it != m_Groups.end(); it++)
	{
		Group *group = *it;
		Group* newGroup = NULL;
		try
		{
			newGroup = new Group(*group, directory);
			newGroup->SetGroupName(group->GetGroupName());
			newChain->AddGroup(newGroup);
			Debug::PrintDebugMsg("Cloned group");
		}
		catch(std::bad_alloc *e) //memory allocation failed
		{
			e = NULL;
			Logger::LogMessage("ERROR: memory allocation failed in Chain::CloneFromVertexDirectoryAndUpdateIt. group wasn't created and wasn't added to the chain.");
			continue;
		}
	}

	Debug::PrintDebugMsg("Chain cloned");
	newChain->SetLastGroupFromPermutaionsIndex(m_LastGroupFromPermutaionsIndex);
	return newChain;
}

//----------------------------------------------------------------------------------
// GetNextGroupIndex: returns a new unused group name
//----------------------------------------------------------------------------------
int Chain::GetNextGroupIndex()
{
	return GetMaxGroupIndex()+1;
}

//----------------------------------------------------------------------------------
// GetLength: returns the number of groups in the chain
//----------------------------------------------------------------------------------
int Chain::GetLength()
{
	return m_Length;
}

//----------------------------------------------------------------------------------
// SetLastGroupFromPermutaionsIndex
// set the index of the last group in this chain that was created
// in the permutaions phase.
//
// @param index
//		the last Group From Permutaions Index (first group in the chain has index 0)
//----------------------------------------------------------------------------------
void Chain::SetLastGroupFromPermutaionsIndex(int index)
{
	m_LastGroupFromPermutaionsIndex = index;
}

//----------------------------------------------------------------------------------
// GetLastGroupFromPermutaionsIndex
// returns the index of the last group in this chain that was created
// in the permutaions phase.
//
// @return int
//		the last Group From Permutaions Index (first group in the chain has index 0)
//----------------------------------------------------------------------------------
int  Chain::GetLastGroupFromPermutaionsIndex()
{
	return m_LastGroupFromPermutaionsIndex;
}

//----------------------------------------------------------------------------------
// Private
//----------------------------------------------------------------------------------

//----------------------------------------------------------------------------------
// CreateGroups
// this is a helper method used in the ctor to create the groups in this chain
//----------------------------------------------------------------------------------
void Chain::CreateGroups(ChainParser &chainFile)
{
	m_Length = chainFile.GetNumberOfGroups();
	map<vector<bool>, Vertex*>* mapForGraph = MakeDirectoryPointerMap();
	if(mapForGraph == NULL)
		throw(new GraphColoringException("unable to create chain. reson: MakeDirectoryPointerMap failed."));

	int *chainGroupSummery = chainFile.GetGroupSummary();
	//go over all the groups in the file
	for(int i=1; i <= m_Length; i++)
	{
		vector<bool> *vertexName = chainFile.GetFirstVertex(i);
		int groupName = i; //group name == group index in the chain file
		int groupSize = chainGroupSummery[i-1];
		Group* group;
		try
		{
			group = new Group(groupName);
		}
		catch(std::bad_alloc *e) //memory allocation failed
		{
			e=NULL;
			Logger::LogMessage("ERROR: memory allocation failed in Chain::CreateGroups. group wasn't created.");
			continue;
		}
		
		//go over all the vertices in the group
		while(vertexName != NULL)
		{
			//get the vertex from the directory
			Vertex* vertex = NULL;
			if(m_VertexDirectory == NULL)
				vertex = VertexDirectory::GetStaticCopyVertex(*vertexName);
			else
				vertex = m_VertexDirectory->GetWorkingCopyVertex(*vertexName);
			if(vertex == NULL)
				throw(new GraphColoringException("vertex not found in directory. initating from chain file failed!"));

			group->InsertNewVertex(vertex); //insert the vertex to the group
			mapForGraph->erase(*vertexName); //remove the vertex from the map that will build the graph

			delete vertexName; // getNextVertex and getFirstVertex allocat memory for the vertex
			vertexName = chainFile.GetNextVertex();
		}
		
		m_Groups.push_back(group);
		m_GroupNames.insert(group->GetGroupName());
		char buffer[10];
		_itoa_s(group->GetGroupName(), buffer,10,10);
		string msg = "Saved group ";
		msg.append(buffer);
		Debug::PrintDebugMsg(msg);
	}

	//at this point, all vertices from the directory, that belong to a group, are in a group
	// and also their container is updated to be their group.

	// update the graph:
	// create a list of vertices from the map and insert all the vertices in it to the graph
	// relater to the chain. This will also update the container of the vertices in the graph.
	list<Vertex*> listForGraph;
	map<vector<bool>, Vertex*>::iterator it = mapForGraph->begin();
	for(; it != mapForGraph->end(); it++)
	{
		listForGraph.push_front(it->second);
	}
	m_Graph->AddVertices(listForGraph);

	delete mapForGraph;

	Debug::PrintDebugMsg("Saved graph");

}


//----------------------------------------------------------------------------------
// makeDirectoryPointerList
// makes a map of new pointers to the vertices in the directory
// does not copy the vertices, only creats new pointers for them.
// @return 
//		on sucsess	- a pointer to the new created map of pointers (allocates memory) 
//		on fail		- NULL
//----------------------------------------------------------------------------------
map<vector<bool>, Vertex*>* Chain::MakeDirectoryPointerMap()
{
	map<vector<bool>, Vertex*>* mapOfDirectory = NULL;
	map<vector<bool>, Vertex*>* newPointers = NULL;
	try
	{
		newPointers = new map<vector<bool>, Vertex*>();
	}
	catch(std::bad_alloc *e)
	{
		e = NULL;
		Logger::LogMessage("memory allocation failed at: Chain::MakeDirectoryPointerMap");
		return NULL;
	}

	if(m_VertexDirectory != NULL)
		mapOfDirectory = m_VertexDirectory->GetWorkingCopyVertices();
	else
		mapOfDirectory = VertexDirectory::GetStaticCopyVertices();

	map<vector<bool>, Vertex*>::iterator it = mapOfDirectory->begin();
	for(; it != mapOfDirectory->end(); it++)
	{
		Vertex** newVertexPtr = NULL;
		try
		{
			newVertexPtr = new Vertex*();
		}
		catch(std::bad_alloc *e)
		{
			e=NULL;
			newPointers->clear();
			delete newPointers;
			return NULL;
		}
		*newVertexPtr	= it->second;
		newPointers->insert(pair<vector<bool>, Vertex*>(it->first, *newVertexPtr));
	}

	return newPointers;
}

//----------------------------------------------------------------------------------
// Print
// prints all groups
//----------------------------------------------------------------------------------
void Chain::Print()
{
	list<Group*> groups = this->ChainGroups();
	list<Group*>::iterator it;
	for (it = groups.begin(); it != groups.end(); it ++)
	{
		Group *group = *it;
		std::stringstream streamStr;
		streamStr <<"# " << group->GetGroupName();
		Logger::LogMessage(streamStr.str());
		group->Print();
	}
}